<?php

/**
 * 链地址法（拉链法）
将所有的相同Hash值的key放在一个链表中，比如key3和key14在hash之后都是0，那么在数组的键为0的地方以链表的形式存储这两个值。
 * 这样，无论有多少个冲突，都只是在当前位置给单链表增加节点。
 * Class searchhash2
 */

// 创建类，用来存储key和value的值，并且存储相同hash的另一个元素。
class HashNode
{
    public $key;
    public $value;
    public $nextNode;
    public function __construct($key, $value){
        $this->key = $key;              // 节点的关键字
        $this->value = $value;          // 节点的值
        $this->nextNode = null;    // 指向具有相同Hash值节点的指针
    }
}
class HashTable3
{
    public $table = array();
    public $size = 12;
    // 简单hash算法。输入key，输出hash后的整数
    public function key2Hash($key)
    {
        return $key % $this->size;
    }
    // 赋值
    public function set($key, $value)
    {
        $key = $this->key2Hash($key);
        if(isset($this->table[$key])){
            //有hash冲突
            $current = $this->table[$key];
            while (!is_null($current->nextNode)){
                $current = $current->nextNode;
            }
            $current->nextNode = new HashNode($key,$value);
            $this->table[$key] = $current;
        }else{
            //无hash冲突

            $this->table[$key] = new HashNode($key,$value);
        }

        return true;
    }
    // 取值
    public function get($key)
    {
        $hash = $this->key2Hash($key);
        $current = $this->table[$hash];
        while (!is_null($current)) {
            if ($current->key == $key) {
                return $current->value;
            }
            $current = $current->nextNode;
        }
        return null;
    }
    // 哈希查找
    public function hashSearch($key)
    {
        $hash = $this->key2Hash($key);
        $current = $this->table[$hash];
        while (isset($current)) { //遍历当前链表
            if ($current->key == $key){  //比较当前节点的关键字
                return $current->value;  //查找成功
            }
            $current = $current->nextNode;  //比较下一个节点
        }
        return null;  //查找失败

    }
}
//测试
$ht = new HashTable3();
$keys = [12, 67, 56, 16, 25, 37, 22, 29, 15, 47, 48, 34];
for ($i = 0; $i < count($keys); $i++) {
    $key = $keys[$i];
    $ht->set($key, $key);
}
echo '<pre>';
print_r($ht->table);
//var_dump($ht->table);
echo '</pre>';



